# 二叉树最大宽度: https://leetcode-cn.com/problems/maximum-width-of-binary-tree/submissions/

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


from collections import deque
class Solution:
    def widthOfBinaryTree(self, root: TreeNode) -> int:
        """
            整到题目，一定要明白一句话： 这个二叉树与满二叉树（full binary tree）结构相同！
            我们需要对每一层，出现的节点进行编号， 下标从1开始， 根节点为 i ，那么左右子节点为 2 * i  和 2 * i + 1， 
            这是完全二叉树的特性。利用根节点，可以使每个子节点 排出编号。
            题目中的数，可以理解为，就是完全二叉树，然后扣去其中一些节点变为了None。但存在的节点，编号不变，因为是满二叉树。
            所以题目中要求算的距离，要加上中间为 None的。 其实就是
            每一行的最右编号， 减去最左编号 加1， 就是当前行的 宽度。

            使用层序遍历解题
        """
        maxWidth = 0
        d = deque()
        d.append((root, 1))
        while d:
            n = len(d)
            left = right = 0
            for i in range(n):
                node_i = d.popleft()
                node = node_i[0]
                index = node_i[1]
                if i == 0:
                    left = index
                if i == n - 1:
                    right = index

                # 编号
                if node.left: d.append((node.left, index * 2))
                if node.right: d.append((node.right, index * 2 + 1))

            maxWidth = max(maxWidth, right - left + 1)
        
        return maxWidth


# 下面是深度优先遍历
"""
    深度优先需要维护两个数组，start， end. 表示每一层的开始 和结束编号， 然后再遍历的时候，
    记录这俩下标，然后再返回最大宽度值
"""
